package me.timlong;

import java.util.Scanner;

public class MaxSubString {

    public String maxSubString(String str1, String str2){
        int len1 = str1.length();
        int len2 = str2.length();

        int[][] dp = new int[len1][len2];

        int maxLen = 0;
        int maxEnd = 0;

        for (int i = 0; i < len2; i++)
            if(str1.charAt(0) == str2.charAt(i))
                dp[0][i] = 1;

        for (int i = 0; i < len1; i++)
            if(str2.charAt(0) == str1.charAt(i))
                dp[i][0] = 1;

        for (int i = 1; i < len1; i++) {
            for (int j = 1; j < len2; j++) {
                if(str1.charAt(i) == str2.charAt(j))
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                if(dp[i][j] > maxLen){
                    maxLen = dp[i][j];
                    maxEnd = i;
                }
            }
        }

        if(0 == maxLen)
            return null;

        return str1.substring(maxEnd - maxLen + 1, maxEnd + 1);

    }


    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        String str1 = sc.nextLine();
//        String str2 = sc.nextLine();
//
//        StringBuilder result = new StringBuilder();
//
//        // 固定str2，从对齐首个char开始滑动
//        for (int i = 0; i < str2.length(); i++) {
//            StringBuilder sb = new StringBuilder();
//            for (int j = 0; j < str1.length() && i + j < str2.length(); j++) {
//                if(str2.charAt(i + j) == str1.charAt(j))
//                    sb.append(str1.charAt(j));
//                else{
//                    result = result.length() >= sb.length() ? result : sb;
//                    sb.delete(0, sb.length());
//                }
//            }
//            result = result.length() >= sb.length() ? result : sb;
//        }
//
//        // 固定str1，从对齐首个char开始滑动
//        for (int i = 0; i < str1.length(); i++) {
//            StringBuilder sb = new StringBuilder();
//            for (int j = 0; j < str2.length() && i + j < str1.length(); j++) {
//                if(str1.charAt(i + j) == str2.charAt(j))
//                    sb.append(str2.charAt(j));
//                else{
//                    result = result.length() >= sb.length() ? result : sb;
//                    sb.delete(0, sb.length());
//                }
//            }
//            result = result.length() >= sb.length() ? result : sb;
//        }
//
//        System.out.println(result.toString());


        System.out.println(new MaxSubString().maxSubString("++fjakfj++", "---dkfsafjsdakfjajfkaj--"));

    }

}
